\section{Algoritmo de busqueda local}
\label{sec::local}

\subsection{Algoritmo y correctitud}

Se implement\'o como tercer m\'etodo un algoritmo de b\'usqueda local
para resolver el problema del trabajo pr\'actico.

El pseudoc\'odigo de este algoritmo se encuentra en la 
figura~\ref{algo::localabs}.

\begin{algorithm}[H] 
	\caption{Pseudoc\'odigo para el algoritmo de busqueda local (general)
	para  resolver el problema de m\'inimo conjunto dominante.}
	\label{algo::localabs}
	\begin{algorithmic}
		\Function{local}{$G = (V,E), C \subseteq V$ compo. conexa, $solIni$}
			\State $mejor \gets solIni$
			\State $solucion \gets solIni$
			\While{$\neg criterioParada $}
				\State $candidata \gets solucion$
				\ForAll{$vecina \in vecindad(sol)$}
					\If{$vecina$ es mejor que $candidata$}
						\State $cantidata \gets vecina$
					\EndIf
				\EndFor
				\State $solucion \gets candidata$
				\If{$solucion$ es mejor que $mejor$}
					\State $mejor \gets solucion$
				\EndIf
			\EndWhile
			\State \Return $mejor$
		\EndFunction
	\end{algorithmic}
\end{algorithm}

El algoritmo, como se puede ver, consiste en iterativamente,
empezando en una soluci\'on candidata, tratar de mejorar la misma 
realizando pasos a soluciones ``vecinas'', hasta que se cumple un
criterio de parada.

Si bien el algoritmo~\ref{algo::localabs} da una idea de como es el
algoritmo en si, deja libre varias funciones y partes de la 
implementaci\'on. Por ejemplo, no especifica cual es el criterio de
parada, que es la vecindad y cuando una soluci\'on es mejor que la otra.

Para nuestra implementaci\'on tomamos las siguientes decisiones.

\begin{itemize}
	\item \textbf{Criterio de parada:} Como criterio de parada elegimos
	cantidad de iteraciones desde que la soluci\'on no fue mejorada.
	De esta manera, podemos acotar el tiempo de ejecuci\'on de manera
	sencilla. La cantidad de iteraciones se puede definir antes de
	realizar la b\'usqueda local, lo cual permite experimentar con 
	valores \'optimos para este.
	
	Se eligi\'o este criterio por su simplicidad y por el hecho de 
	permitir acotar la cantidad de iteraciones de la busqueda local pero
	al mismo tiempo sin restrigir fuertemente la cantidad de mejoras
	posibles a realizar (ya que lo que restringimos es la cantidad de
	iteraciones entre mejoras a la soluci\'on, no la cantidad de 
	iteraciones totales). Si bien este criterio puede generar una 
	cantidad de iteraciones innecesaria (por ejemplo, si llegamos
	a un m\'inimo conjunto dominante se gastar\'an todas las iteraciones
	intentando encontrar una soluci\'on mejor sin exito), es m\'as 
	flexible en los casos en que la soluci\'on se queda temporalmente
	trabada en un m\'inimo local.
	
	\item \textbf{Vecindad de una soluci\'on: } Consideramos como 
	soluci\'on a todo conjunto dominante de la componente conexa.
	Una soluci\'on $S'$ se considera vecina de la soluci\'on $S$ si
	difiere en un nodo y tiene igual o menor cantidad de nodo. En 
	concreto, esta vecindad se calcula tratando de remover un nodo y si
	esto no es posible, cambiar un nodo por otro (operaci\'on a la que
	a partir de ahora nos refereriremos como \textit{swapping}).
	
	Se consideraron otras vecindades, como por ejemplo reemplazar dos
	nodos por uno solo, pero se descart\'o en base a que incrementaban
	de manera excesiva el c\'omputo necesario (en las implementaciones
	b\'asicas consideradas por lo menos) sin extender mucho la cantidad
	de elementos de la vecindad. Nos pareci\'o tambi\'en que con estas
	dos operaciones pod\'ia generarse una vecindad interesante. En
	particular la operaci\'on de \textit{swapping} se eligi\'o con el
	prop\'osito de introducir algo de perturbaci\'on en soluciones que
	est\'an trabadas en un m\'inimo local, de manera que se pudiera
	salir de estos y llegar a mejores soluciones.
	
	Una consideraci\'on adicional que tuvimos es que para evitar que
	el programa cicle realizando \textit{swapping} del mismo par de 
	nodos, se tom\'o la decisi\'on de que solo se puede intercambiar 
	un nodo por otro si el primero tiene un \'indice mayor en la
	numeraci\'on del grafo. Si bien
	esto limita la cantidad de intercambios que se puede realizar, 
	evita que se gasten intercambios in\'utiles en una cadena (lo cual
	no contribuye a mejorar la soluci\'on). 
	
	\item \textbf{Comparaci\'on de soluciones: } Una soluci\'on se
	considera mejor que otra si tiene menos nodos. Esto corresponde
	directamente al criterio de minimalidad de un conjunto dominante, y
	por lo tanto esta condici\'on es la ideal para saltar. En el caso
	de considerar soluciones con un nodo menos, para quedarnos con la
	mejor el criterio de decisi\'on es que el nodo removido sea del 
	menor grado posible. El prop\'osito es que un nodo de menor grado
	domina menor cantidad de nodos, y por lo tanto hay 
	m\'as posibilidades de que se siga pudiendo remover nodos de la
	soluci\'on manteni\'endose que sea un conjunto dominante. De manera
	an\'aloga, para el caso de intercambiar dos nodos, se elige como
	criterio de desempate entre soluciones que cambie un nodo de grado
	m\'inimo dentro de la soluci\'on. 

	\item \textbf{Soluci\'on inicial: } Si bien implementamos una 
	funci\'on que toma con que soluci\'on inicial empieza a iterar, por
	motivos de comodidad para la implementaci\'on posterior de la 
	metaheur\'istica GRASP, la b\'usqueda local en si necesita una 
	soluci\'on inicial. Con este prop\'osito utilizamos como soluci\'on
	inicial la que consiste en todos los nodos de la componente conexa.
	La elegimos por el bajo costo computacional principalmente por el
	bajo costo computacional asociado a obtener el conjunto, y porque
	es un buen punto de partida para aplicar una serie de pasos como
	los descriptos anteriormente (que consisten en por ejemplo retirar
	nodos que no sirvan, cosa que es relativamente sencilla en la 
	soluci\'on de todos los nodos). 
\end{itemize}

Estas modificaciones pueden verse en en el pseudoc\'odigo presentado
en el Algoritmo~\ref{algo::local}.

\begin{algorithm}
	\caption{Pseudoc\'odigo para el algoritmo de busqueda local para 
	resolver el problema de m\'inimo conjunto dominante. Se detalla la
	condici\'on de parada y la definici\'on de vecindad elegidas.}
	\label{algo::local}
	\begin{algorithmic}
		\State \Comment{Iteraciones maximas sin mejorar}
		\State \Param $MAXITERS$
		\Statex
		\Function{local}{$G = (V,E), C \subseteq V$ compo. conexa, $solIni$}
			\State $mejor \gets solIni$
			\State $S \gets solIni$
			\State $sinMejorar \gets 0$
			\While{$sinMejorar < MAXITERS$}
				\State $candidata \gets solucion$
				\State $gradoMin \gets | C | + 1$
				\ForAll{nodo $v \in S$}
					\If{$S \backslash v$ es dominante $\wedge grado(v) < gradoMin$ }
						\State $gradoMin \gets grado(v)$	
						\State $cantidata \gets S \backslash v$
					\EndIf
				\EndFor
				\If{$| S | < mejor$}
					\State $sinMejorar \gets 0$
					\State \Continue
				\EndIf			
				\State \Var $s,t,$
				\State \Var $gradoMax \gets 0$
				\ForAll{$v \in S, w \in C \backslash S$}
					\If{$S \backslash v \bigcup \{ w \}$ es dominante $\wedge v > w \wedge grado(v) > gradoMax$ }
						\State $gradoMax \gets grado(v)$
						\State $s \gets v$
						\State $t \gets w$
					\EndIf
				\EndFor
				\If{$\neq \exists s,t, s > t : S \backslash v \bigcup w$ es dominante}
					\State \Break
				\Else
					\State $S \gets S \backslash \{ v \} \bigcup \{ w \}$
				\EndIf
			\EndWhile
		\EndFunction
	\end{algorithmic}
\end{algorithm}

Para demostrar la necesidad de agregar la heur\'istica de intercambio
de nodos, podemos considerar el grafo de Petersen. El mismo tiene la
siguiente forma:

\begin{figure}[H]
	\caption{Grafo de Petersen. Este grafo nos sirve de ejemplo de 
	porque es necesaria la estrategia de intercambio de nodos para
	b\'usqueda local.}
	\label{fig::petersen}
	\centering
	\includegraphics[width=0.3\textwidth]{img/petersen.pdf}
\end{figure} 

El n\'umero de dominaci\'on (es decir la cardinalidad de un m\'inimo
conjunto dominante de este grafo) es 3, por ejemplo $\{ 1,3,7\}$. 
Sin embargo, la b\'squeda local presentada anteriormente devuelve un 
conjunto de cardinalidad 5.

La raz\'on es la siguiente. Supongamos que aplicamos la estrategia. 
Puesto que todos los nodos pueden sacarse y todos tienen igual grado,
el algoritmo de b\'usqueda local iterativamente remueve los nodos de
la estrella interior, dejando nada m\'as los de la c\'ascara, 
devolviendo as\' un conjunto dominante de 5 nodos que es sub\'optimo en
t\'erminos de la cantidad de nodos necesarios.

Al agregar la estrategia de intercambio de nodos, permitimos perturbar
la soluci\'on por ejemplo cambiando el nodo 10 por el nodo 2. De esta
manera, ahora podemos retirar m\'as nodos lo cual si nos permite 
alcanzar un \'optimo.

Si bien se puede argumentar que es rol de otras partes de una 
metaheur\'istica (por ejemplo, el algoritmo goloso
randomizado que es la primer parte de la metaheur\'istica GRASP,ver
secci\'on~\ref{sec::grasp}) la generaci\'on de soluciones iniciales,
con lo cual el rol de la b\'usqueda local debiera ser m\'as bien
reducido, nos pareci\'o que la perturbaci\'on de soluciones mediante
intercambio de nodos permit\'ia fortalecer la b\'usqueda local, ya
que utilizando \'unicamente remoci\'on de nodos ocurr\'ian casos de
suboptimalidad como el presentado anteriormente, por un costo 
computacional m\'as razonable que otros m\'etodos (como por ejemplo,
tratar de reemplazar dos nodos por uno en la soluci\'on, implementado
de manera trivial).

Un detalle que consideraremos posteriormente (cuando hagamos el 
an\'alisis experimental de los algoritmos presentados) es que cota 
debemos poner para la cantidad de iteraciones. Si la cantidad de 
iteraciones es muy baja, ganamos en tiempo de ejecuci\'on pero las 
soluciones obtenidas podr\'ian ser potencialmente muy malas. Por lo 
tanto hay un intercambio entre calidad de las soluciones y tiempo de
ejecuci\'on.

En primera instancia entonces analizaremos la complejidad del algoritmo
asumiendo que sabemos que $c$ es la cantidad de iteraciones.

\subsection{Implementaci\'on en C++ y complejidad}

El cuerpo interior de la b\'usqueda local realiza dos operaciones: 
Tratar de eliminar un nodo y, en caso de no poder encontrar ninguno, 
tratar de intercambiar dos nodos. 

Nuevamente, miraremos en este caso la complejidad para la componente
conexa que se esta analizando, la cual suponemos tiene $n$ nodos y $m$ 
aristas.

La primera de las operaciones se implement\'o de la siguiente manera:
Se prueba todos los nodos de la soluci\'on buscando saber si removiendo
este el conjunto sigue siendo dominante. Para realizar esto se 
program\'o una funci\'on adicional (\texttt{dominaComponente}) que 
recibe un conjunto y (posiblemente) un nodo a ignorar. Lo que hace 
entonces es revisar si usando todos los nodos del conjunto excepto el
que le pasamos que ignore, se domina toda la componente conexa.

Para implementar este chequeo, utilizamos un vector auxiliar de enteros,
del tama\~no de la cantidad de nodos del grafo, que inicializamos en 0.
Posteriormente recorremos todos los nodos del conjunto y lo marcamos a
\'el y sus vecinos en el conjunto (evitando por supuesto el nodo pasado
por par\'ametro). Finalmente hacemos una pasada por todos los nodos de
la componente para ver si estos fueron marcados como dominados. Si as\'i
fue entonces el conjunto es dominante.

Sin bien no es necesario instanciar un vector de tama\~no todos los 
nodos del grafo, se prefiri\'o hacerlo as\'i por simplicidad del 
c\'odigo posterior. Asumiremos que asignar memoria depende solamente del
asignador del sistema operativo, y que por lo tanto esto es una 
constante $O(1)$ (porque el costo de reacomodar los bloques de memoria
para hacer el espacio no es dependiente de los par\'ametros del programa,
sino de otros factores externos). 

Dado que para cada nodo de la soluci\'on excepto el que ignor\'amos,
recorremos todos sus vecinos para marcarlos, y luego recorremos todos
los nodos de la componente conexa para saber si est\'an o no dominados, 
tenemos que la complejidad de esta funci\'on es $O(n+m)$, porque en peor
caso recorremos todos los nodos de la componente y todas las aristas
del grafo (al mirar los vecinos de todos los nodos) ya que un conjunto
dominante tiene como m\'aximo la misma cantidad de nodos que el conjunto
original (de hecho puede tener como m\'aximo la mitad para grafos
conexos como vimos en la secci\'on~\ref{sec::exacto}).

Ahora que sabemos el costo de este chequeo, podemos determinar el costo 
de la primer parte del cuerpo de la b\'usqueda local (donde revisamos 
de retirar un nodo). La misma itera sobre todos los nodos de la 
soluci\'on y marca este como el nodo a ignorar. Salvo operaciones $O(1)$
bajo el modelo uniforme como operaciones entre variables de tipos nativos
del lengauje C++, la \'unica llamada que incrementa la complejidad es
la llamada a la funci\'on \texttt{esDominante}. Por lo tanto, el costo
total de esta parte es $O(n \cdot (n+m))$.

El costo de, dado que encontramos un nodo que podemos eliminar, 
actualizar la soluci\'on \'optima es $O(1)$. Esto es porque, para 
eliminar el nodo, lo movemos a la parte de atr\'as del vector y 
eliminamos el \'ultimo elemento del mismo, operaci\'on que tiene costo
constante. Dado que la soluci\'on siempre mejora o se mantiene igual,
con respecto a la cantidad de nodos que contiene, solo necesitamos contar 
cuantas veces vamos sin haber mejorado la soluci\'on desde la \'ultima 
vez (lo cual es sencillo). Por lo tanto, dado que todas las operaciones
consisten en operaciones $O(1)$ sobre tipos de datos, u operaciones sobre
tipos nativos del lenguaje, esta parte del cuerpo de la b\'squeda local
tiene complejidad $O(1)$.

Finalmente, la implementaci\'on de intercambio de nodos se realiza
de la siguiente manera: Iteramos sobre todos los nodos de la componente
conexa. Si este se encuentra en el conjunto soluci\'on, no lo 
consideramos. Luego, buscamos si alguno de todos los otros nodos del
conjunto soluci\'on se puede cambiar por ese de manera que siga siendo
dominante. Para ello lo que hacemos es intercambiarlos en la soluci\'on
y luego llamar a \texttt{esDominante}. Para que no ignore ninguno de los
nodos de la soluci\'on, aprovechamos que los nodos se indexan desde cero,
y le pasamos -1 como nodo a ignorar (Que como es imposibel que este en
la soluci\'on, nunca va a ser encontrado). Finalmente, intercambiamos
los el nodo de grado m\'as grande que se puede intercambiar por alguno
en la soluci\'on.

El costo de iterar por todos los nodos de la componente es $O(n)$. El
costo de iterar por todos los nodos de la soluci\'on lo acotamos por
$O(n)$ tambi\'en, como vimos antes. Esto implica que el costo de 
determinar si un nodo esta o no en la soluci\'on (que se utiliza antes
de iterar para ver si se puede usar en un intercambio) es $O(n)$, puesto
que la funci\'on \texttt{find} de C++ recorre linealmente los elementos
entre los dos iteradores pasados buscando el elemento pasado como clave.
~\ref{cppfind}
El costo de la operaci\'on
\texttt{queDominaria} ya lo acotamos por $O(n+m)$. Puesto que el resto
de las operaciones consiste en indexar vectores (lo cual tiene costo 
$O(1)$ por estar implementados sobre arreglos redimensionables),
tenemos entonces un costo de $O(n \cdot n \cdot (n+m))$ = $O(n^3 + n^2 m)$

Resta entonces acotar la cantidad de iteraciones de la b\'usqueda local,
teniendo en cuenta el par\'ametro $c$ de iteraciones sin mejorar.

Observemos que solo se puede mejorar la soluci\'on una cantidad $n-1$ de
veces (puesto que empezamos con todos los nodos, lo mejor que podr\'iamos
hacer es retirar nodos uno por uno hasta que quede uno solo). Suponiendo
que entre mejoras necesitamos hacer una cantidad de \textit{swaps} que
requiera iterar $c$ veces, entonces tendremos un total de $nc$ iteraciones.

Por lo tanto podemos acotar la complejidad por algo $O(nc(n^3 + n^2 m))$
por lo tanto el algoritmo es $O(n^3c + n^2 m c)$.
